package com.example.demo.剑指offer;

import com.example.demo.剑指offer.删除链表的节点.ListNode;

/**
 * @author：zzc
 * @date: 2022/8/19
 */
public class 合并两个排序的链表 {

    //输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
    //
    //示例1：
    //
    //输入：1->2->4, 1->3->4
    //输出：1->1->2->3->4->4

    //注意：本题与主站 21 题相同：https://leetcode.cn/problems/merge-two-sorted-lists/

    //解法
    //同时遍历两个链表，归并插入新链表中即可。

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    class Solution {

        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(0);
            ListNode p = dummy;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    p.next = l1;
                    l1 = l1.next;
                } else {
                    p.next = l2;
                    l2 = l2.next;
                }
                p = p.next;
            }
            p.next = l1 == null ? l2 : l1;
            return dummy.next;
        }
    }



}
